/*
 * IncidenceList CLASS TEMPLATE
 * ...
 *
 */

#ifndef UNITRAF_GRAPHTRAITS_ADJACENCYLIST_HPP
#define UNITRAF_GRAPHTRAITS_ADJACENCYLIST_HPP

#include <graph\traits\Traits.hpp>
#include <graph\traits\Edge.hpp>
#include <graph\traits\Vertex.hpp>
#include <Exceptions.hpp>


#ifndef VALID
#define VALID 1
#endif

#ifndef INVALID
#define INVALID 0
#endif


namespace unitraf {

// Making aliases
using std::set;
using std::map;
using std::list;

namespace graph_traits {

/////////////////////////////////////////////////////////////////////////////
// ADJACENCY LIST DETAILS

template<class _VertexProperty, class _EdgeProperty, class _Directed> 
  class IncidenceList;

template<class _VertexProperty, class _EdgeProperty> 
  class IncidenceList<_VertexProperty, _EdgeProperty, directed_tag> {
    
    typedef IncidenceList _myt;

   public:
    ////////////////////////////////////////////////////////////////////////////     
    // PUBLIC INTERFACE

    // Vertex type obtaining given property
    typedef Vertex<_VertexProperty> vertex_type;
    // Plain vertex type
    typedef Vertex<no_property_tag> vertex_descriptor;
    
    // Edge type obtaining given property
    typedef Edge<_EdgeProperty> edge_type;
    // Plain edge type
    typedef Edge<no_property_tag> edge_descriptor;

    
    // If graph is represented as:
    //  G = (V, E), this is E/(E)dges.
    typedef set<edge_type> edge_set;
        
        // If graph is represented as:
    //  G = (V, E), this is V/(V)ertices.
    typedef set<vertex_type> vertex_set;

    // ADJACENCY LIST TYPE: META STORAGE
    typedef map<  vertex_descriptor, 
                  list<edge_descriptor> > incidence_map_type;
        

    // Vertex iterator implementation
    // Edge iterator implementation
    template<class _BaseIter>
      class VertexIterator 
        : public IteratorAdaptor<VertexIterator<_BaseIter>, _BaseIter> {

          typedef IteratorAdaptor<VertexIterator<_BaseIter>, _BaseIter> _base;

         public:
          /////////////////////////////////////////////////////////////////////
          // PUBLIC INTERFACE
           
          typedef _BaseIter base_iterator;

          VertexIterator() 
            {};

          VertexIterator(const base_iterator& iterator) 
            : _base(iterator) {};

      };

    typedef VertexIterator<
              typename vertex_set::const_iterator >  // Base iterator type
                vertex_iterator;

    
    // Edge iterator implementation
    template<class _BaseIter> 
      class EdgeIterator 
        : public IteratorAdaptor<EdgeIterator<_BaseIter>, _BaseIter> {

          typedef IteratorAdaptor<EdgeIterator<_BaseIter>, _BaseIter> _base;

         public:
          /////////////////////////////////////////////////////////////////////
          // PUBLIC INTERFACE

          typedef _BaseIter base_iterator;

          EdgeIterator() 
            {};

          EdgeIterator(const base_iterator& iterator) 
            : _base(iterator) {};

      };

    typedef EdgeIterator<
              typename edge_set::const_iterator >  // Base iterator type
                edge_iterator;


    // Out-Vertex iterator implementation
    template<class _ValTy, class _BaseIter> 
      class OutVertexIterator 
        : public IteratorAdaptor< OutVertexIterator<_ValTy, _BaseIter>, _BaseIter > {

        typedef IteratorAdaptor< OutVertexIterator, _BaseIter > _base;
        
       public:
        ///////////////////////////////////////////////////////////////////////////
        // PUBLIC INTERFACE

        typedef _BaseIter base_iterator;
        typedef _ValTy    value_type;
        typedef _ValTy*   pointer;
        typedef _ValTy&   reference;

        OutVertexIterator() 
          : V_(0) {};
       
        OutVertexIterator(const base_iterator& iterator, const vertex_set& V) 
          : _base(iterator), V_(&V) {};


        reference operator*() {
          vertex_set::iterator referrent = 
            V_->find(                                   // Find vertex with given ID
              value_type(                               // Construct pseudo-vertex wrapping around given ID
                _DERIVE_FIRST(_base::operator*())));    // Derive vertex ID from mapping:
                                                        //  vertex_id -> { ... }
          // Check for consistency
          assert(referrent != V_->end());
          return (*referrent);
        };

        pointer operator->() {
          return &(operator*());
        };


       private:
        ///////////////////////////////////////////////////////////////////////
        // REPRESENTATION
        
        const vertex_set * const V_;

      };
      
    typedef 
      OutVertexIterator<  vertex_type const,                    // Referenced value type
                          incidence_map_type::const_iterator >  // Base iterator type
        out_vertex_iterator;
   

    // Out-edge iterator implementation
    template<class _ValTy, class _BaseIter>
      class OutEdgeIterator 
        : public IteratorAdaptor< OutEdgeIterator<_ValTy, _BaseIter>, _BaseIter > {

        typedef IteratorAdaptor< OutEdgeIterator, _BaseIter > _base;
                    
       public:
        ///////////////////////////////////////////////////////////////////////////
        // PUBLIC INTERFACE

        typedef _BaseIter base_iterator;
        typedef _ValTy value_type;
        typedef _ValTy* pointer;
        typedef _ValTy& reference;

        OutEdgeIterator() 
          : E_(0) {};
    
        OutEdgeIterator(const base_iterator& iterator, const edge_set& E) 
          : _base(iterator), E_(&E) {};

        
        reference operator*() {
          edge_set::iterator referrent = 
            E_->find(                     // Find edge connecting vertices with given IDs
              value_type(                 // Construct pseudo-edge wrapping around plain edge object
                (_base::operator*())));   // Reference plain edge object
          
          // Check for consistency
          assert(referrent != E_->end());
          return (*referrent);
        };

        pointer operator->() {
          return &(operator*());
        };

       
       private:
        ///////////////////////////////////////////////////////////////////////
        // REPRESENTATION
        
        const edge_set * const E_;

      };
      
    typedef 
      OutEdgeIterator<  edge_type const,                                  // Referenced value type
                        incidence_map_type::mapped_type::const_iterator>  // Base iterator type
        out_edge_iterator;
    

    // Reachable(from given) vertex iterator implementation
    template<class _ValTy, class _OutEdgeIter> 
      class ReachableVertexIterator
        : public IteratorAdaptor< 
                    ReachableVertexIterator<_ValTy, _OutEdgeIter>, 
                    _OutEdgeIter > {
    
        typedef IteratorAdaptor< ReachableVertexIterator, _OutEdgeIter > _base;

       public:
        ///////////////////////////////////////////////////////////////////////////
        // PUBLIC INTERFACE

        typedef _OutEdgeIter base_iterator;
        typedef _ValTy value_type;
        typedef _ValTy* pointer;
        typedef _ValTy& reference;

        ReachableVertexIterator() 
          : V_(0) {};

        ReachableVertexIterator(const base_iterator& iterator, const vertex_set& V) 
          : _base(iterator), V_(&V) {};

        // Derive reference to in-vertex for the given edge
        reference operator*() {
          vertex_set::iterator referrent = 
            V_->find(                       // Find vertex with given ID
              value_type(                   // Construct pseudo-vertex wrapping around given ID
                _base::operator*().target()));  // Derive vertex ID from edge object

          // Check for consistency
          assert(referrent != V_->end());
          return (*referrent);
        };

        // Derive pointer to in-vertex for the given edge
        pointer operator->() {
          return &(operator*());
        };

       private:
        ///////////////////////////////////////////////////////////////////////
        // REPRESENTATION

        const vertex_set * const V_;

      };
      
    typedef
      ReachableVertexIterator<  vertex_type const,  // Referenced value type
                                out_edge_iterator > // Base iterator type
        reachable_vertex_iterator;


      // Container for validated pair of iterators
      template<class _Iter> struct _validated_iterator_pair {

        _validated_iterator_pair() 
          : valid(INVALID) {};

        _validated_iterator_pair(const _Iter& first, const _Iter& last, 
          bool valid = VALID) : first(first), last(last), valid(valid) {};

        
        _Iter first;
        _Iter last;
        
        bool valid;

      };

      // Container for validated iterator
      template<class _Iter> struct _validated_iterator {

        _validated_iterator(bool valid = INVALID) 
          : valid(valid) {};

        _validated_iterator(const _Iter& iterator, bool valid = VALID) 
          : self(iterator), valid(valid) {};


        _Iter self;

        bool valid;

      };
      
    // Pair of { first, last } iterators to the sequence of vertices
    typedef 
      _validated_iterator_pair<vertex_iterator>
        vertex_pairii;

    // Pair of { first, last } iterators to the sequence of out-vertices
    typedef 
      _validated_iterator_pair<out_vertex_iterator> 
        out_vertex_pairii;

    // Pair of { first, last } iterators to the sequence of out-edges
    typedef 
      _validated_iterator_pair<out_edge_iterator> 
        out_edge_pairii;

    // Pair of { first, last } iterator to the sequence of reachable vertices
    typedef 
      _validated_iterator_pair<reachable_vertex_iterator> 
        reachable_vertex_pairii;

    // Pair of { iterator, bool }
    typedef _validated_iterator<vertex_iterator> vertex_vi;

    // Pair of { iterator, bool }
    typedef _validated_iterator<edge_iterator> edge_vi;

    // Pair of { iterator, bool }
    typedef _validated_iterator<out_vertex_iterator> out_vertex_vi;
    
    // Pair of { iterator, bool }
    typedef _validated_iterator<out_edge_iterator> out_edge_vi;
    
    
    // CONSTRUCTORS AND INITIALIZERS

    IncidenceList() {};
    
    template<class _EdgeIter, class _VertexIter> 
      IncidenceList(_VertexIter first_vertex, _VertexIter last_vertex, 
        _EdgeIter first_edge, _EdgeIter last_edge) {
        
          _Vinsert(first_vertex, last_vertex);
          _Einsert(first_edge, last_edge); 

      };

    // DESTRUCTOR

    ~IncidenceList() {};
    

    // METHODS

    // Add given vertex to the vertex set
    bool _Vadd(const vertex_type& vertex) {
      return _DERIVE_SECOND(V_.insert(vertex));
    };

    // Add given edge to the edge set
    bool _Eadd(const edge_type& edge) {
      
      using std::make_pair;

      // For given out-vertex find mapping of it to the list of adjacent edges
      incidence_map_type::iterator mapping = incidence_map_.find(edge.source());

      if (mapping != incidence_map_.end()) {
        
        // Congrats! Derive "adjacency list" from mapping and push_back to it
        _DERIVE_SECOND(*mapping).push_back(edge);
        
        return _DERIVE_SECOND(E_.insert(edge));
      
      } else {
      
        // Check if given edge could exist
        if (V_.find(edge.source()) != V_.end() && V_.find(edge.target()) != V_.end())
          // Insert edge into the E set and append to adjacency list
          return _DERIVE_SECOND(E_.insert(edge))
                  && _DERIVE_SECOND(
                      incidence_map_.insert(
                        make_pair(edge.source(), incidence_map_type::mapped_type(1, edge))));
        else
          throw bad_edge("GIVEN EDGE CONNECTS NON-EXISTENT VERTICES!");

      };

    };

    // Insert given sequence of vertices into the vertex set
    template<class _VertexIter>
      void _Vinsert(_VertexIter first, _VertexIter last) {
        for(; first != last; ++first)
          if (!_Vadd(*first)) assert(INVALID);
      };

    // Insert given sequence of edges into edge set and construct adjacency
    // list
    template<class _EdgeIter>
      void _Einsert(_EdgeIter first, _EdgeIter last) {
        for(; first != last; ++first)
          if (!_Eadd(*first)) assert(INVALID);
      };


#ifdef __INCLUDE_OBSOLETE

    // Derive iterator for given vertex
    out_vertex_vi _find_out_vertex(typename vertex_type::identity_type const& vertex_id) {
      
      if (self_.find(vertex_id) != self_.end())
        return out_vertex_vi(V_.find(vertex_type(vertex_id)), VALID);

      return INVALID;

    };

    // Derive const iterator for given vertex
    out_vertex_vc _find_out_vertex(typename vertex_type::identity_type const& vertex_id) const {
      
      if (self_.find(vertex_id) != self_.end())
        return out_vertex_vc(V_.find(vertex_type(vertex_id)), VALID);

      return INVALID;

    };

    // Derive iterator for given edge
    out_edge_vi _find_out_edge(typename vertex_type::identity_type const& out_vertex_id, 
      typename vertex_type::identity_type const& in_vertex_id) {

        using std::find;
        using std::make_pair;
        
        value_type::iterator adjacency_list_iterator = self_.find(out_vertex_id);

        typename edge_list::iterator found = find(adjacency_list_iterator->second.begin(), 
          adjacency_list_iterator->second.end(), 
          make_pair(out_vertex_id, in_vertex_id));

        return out_edge_vi(found, found != adjacency_list_iterator->second.end());

    };

    // Derive iterator for given edge
    out_edge_vc _find_out_edge(typename vertex_type::identity_type const& out_vertex_id, 
      typename vertex_type::identity_type const& in_vertex_id) const {

        using std::find;
        using std::make_pair;
        
        value_type::iterator adjacency_list_iterator = self_.find(out_vertex_id);

        typename edge_list::iterator found = find(adjacency_list_iterator->second.begin(), 
          adjacency_list_iterator->second.end(), 
          make_pair(out_vertex_id, in_vertex_id));

        return out_edge_vc(found, found != adjacency_list_iterator->second.end());

    };

#endif  // #ifdef __INCLUDE_OBSOLETE

    // Derive iterator to particular vertex
    vertex_vi _get_vertex(const vertex_descriptor& vertex) const {
      
        vertex_set::const_iterator referrent = 
          V_.find(vertex_type(vertex));
        
        return vertex_vi(vertex_iterator(referrent), referrent != V_.end());

    };

    // Derive iterator to particular edge
    edge_vi _get_edge(const vertex_descriptor& source, 
      const vertex_descriptor& target) const {
      
        edge_set::const_iterator referrent = E_.find(edge_type(source, target));
        
        return edge_vi(edge_iterator(referrent), referrent != E_.end());

    };

    // Derive vertices
    vertex_pairii _get_vertices() const {
      return 
        vertex_pairii(
          vertex_iterator(V_.begin()),
          vertex_iterator(V_.end()));
    };

    // Derive vertices with positive out-degree 
    out_vertex_pairii _get_out_vertices() const {
      
      return 
        out_vertex_pairii(
          out_vertex_iterator(incidence_map_.begin(), V_), 
          out_vertex_iterator(incidence_map_.end(), V_));
              
    };

    // Derive outgoing edges of a given vertex
    out_edge_pairii _get_outgoing_edges(const vertex_descriptor& vertex) const {

      // Find incidence list for given vertex
      incidence_map_type::iterator found = incidence_map_.find(vertex);

      // Check whether given vertex has outgoing edges
      if (found == incidence_map_.end())
        return out_edge_pairii();

      return 
        out_edge_pairii(
          out_edge_iterator(_DERIVE_SECOND(*found).begin(), E_), 
          out_edge_iterator(_DERIVE_SECOND(*found).end()), E_);

    };

    
    // Derive vertices adjacent with given vertex
    reachable_vertex_pairii _get_reachable_vertices(const vertex_descriptor& vertex) const {

      // Find incidence list for given vertex
      incidence_map_type::const_iterator found = incidence_map_.find(vertex);

      // Check whether given vertex has outgoing edges
      if (found == incidence_map_.end())
        return reachable_vertex_pairii();
      
      return 
        reachable_vertex_pairii(
          reachable_vertex_iterator(
            out_edge_iterator(_DERIVE_SECOND(*found).begin(), E_), V_),
          reachable_vertex_iterator(
            out_edge_iterator(_DERIVE_SECOND(*found).end(), E_), V_));
            
    };


    // Check's graph integrity
    bool _check_integrity() const { 
      return ((V_.size()) != 0 && (E_.size() != 0));
    };
   
   
   private:
    ////////////////////////////////////////////////////////////////////////////     
    // PRIVATE INTERFACE

    // Prevent copying
    IncidenceList(const IncidenceList&);            /* NOT DEFINED */
    IncidenceList& operator=(const IncidenceList&); /* NOT DEFINED */
    
    ///////////////////////////////////////////////////////////////////////////
    // REPRESENTATION
    
    // Set of the graph's vertices 
    vertex_set V_;

    // Set of the graph's edges
    edge_set E_;

    // Adjacency list of the graph
    incidence_map_type incidence_map_;

};

};  // namespace graph_traits

};  // namespace unitraf

#endif  // #ifndef UNITRAF_GRAPHTRAITS_INCIDENCELIST_HPP